#include <numeric>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#ifdef __GNUC__
#include <ext/hash_map>
using namespace __gnu_cxx;
#else
#include <hash_map>
using namespace stdext;
#endif
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
#define Rep(i,n) for(int i=0;i<(n);++i) 
#define For(i,a,b) for(int i=(a);i<=(b);++i) 
#define ForI(TP,i,coll) for(TP (i)=coll.begin();(i)!=coll.end();(i)++)
#define ForD(i,a,b) for(int i=(a);i>=(b);--i)
#define All(a) a.begin(), a.end()


const int INF=0x0FFFFFFF;
//typedef map<int, VI> M_D_SRC;
typedef hash_map<LL, LL> Cache_Type;

inline double ext(LL v, int power)
{
	double dexp=1.0/power;
	return pow((double)v, dexp);
}

LL po(LL b, int e)
{
	if(e==0) return 1;
	int e2=e>>1;
	LL ret=po(b, e2);
	ret*=ret;
	if(e&0x1)
		ret*=b;
	return ret;
}

struct ThePower
{
	Cache_Type cache;
	LL count(LL n)
	{
		if(n==1)
			return 0;

		LL& ret=cache[n];
		if(ret!=0) return ret;

		ret=n-1;
		For(expo, 2, INF)
		{
			double dval=ext(n, expo);
			int ival=(int)dval;
			if(dval-ival>0.5)
				ival++;

			LL nn=po(ival, expo);
			LL nret= (nn>n ? nn-n : n-nn);
			nret++; // the powerstep
			nret+=count(ival);
			ret=min(nret, ret);

			if(ival<=2)
				return ret;
		}
		return ret;
	}
};

int main()
{
	ThePower po;
#define Test(i) cout<< i <<" : " << po.count(i) <<endl;
	//LL n=100;
	//while(n!=0)
	//{
	//	cout<< po.count(n)<<endl;
	//	cin>> n;
	//}
	Test(2);
	Test(4);
	Test(80);
	Test(84);
	Test(81);
	Test(597007);
	Test(123456789);
	Test(101567597359932145);
	Test(1000000000000000000);
	Test(450283905890997363);
	Test(534223122313218976);
	system("PAUSE");
}
